W2. Logical Equivalence, Normal Forms (DNF, CNF, ANF)

Author

Zakhar Podyakov

Published

September 17, 2025

Quiz | Flashcards

1. Summary

1.1 Logical Formulas and Operators

In logic, a formula (or proposition) is a statement that can be definitively determined as either true or false. Simple formulas, often represented by variables like \(p\) or \(q\), can be combined using logical operators to form more complex formulas.

  • Negation (\(\neg\)): Reverses the truth value of a formula. \(\neg p\) is read as “not p”. If \(p\) is true, \(\neg p\) is false.
  • Conjunction (\(\land\) or &): Represents logical “AND”. The formula \(p \land q\) is true only if both \(p\) and \(q\) are true.
  • Disjunction (\(\lor\)): Represents logical “OR”. The formula \(p \lor q\) is true if at least one of \(p\) or \(q\) is true. It is only false when both are false.
  • Implication (\(\to\)): Represents an “if-then” statement. \(p \to q\) is read as “if p, then q”. It is only false when \(p\) is true and \(q\) is false. In all other cases, it is true.
  • Bi-implication (\(\leftrightarrow\)): Represents “if and only if”. \(p \leftrightarrow q\) is true only when \(p\) and \(q\) have the same truth value (both true or both false).
1.2 Classification of Logical Formulas

Formulas can be classified based on their truth values across all possible interpretations of their variables.

  • Tautology: A formula that is always true, regardless of the truth values of its constituent variables. For example, the formula \(p \lor \neg p\) is always true because a proposition must be either true or false.
  • Contradiction: A formula that is always false. For example, \(p \land \neg p\) is a contradiction because a proposition cannot be both true and false at the same time.
  • Contingency: A formula that is neither a tautology nor a contradiction. Its truth value depends on the truth values of its variables. For example, \(p \lor q\) is a contingency because its truth depends on whether \(p\) or \(q\) is true.
  • Satisfiability: A formula is considered satisfiable if there exists at least one assignment of truth values to its variables that makes the entire formula true. Tautologies and contingencies are satisfiable, while contradictions are not. The problem of determining if a formula is satisfiable is a famous problem in computer science known as the Boolean Satisfiability Problem (SAT), which the Cook-Levin theorem proved to be NP-complete.
1.3 Logical Equivalence

Two formulas are logically equivalent if they have identical truth tables. This means that for every possible combination of truth values for their variables, the two formulas produce the same result. This relationship is denoted by the symbol \(\equiv\). Understanding these equivalences is crucial for simplifying and manipulating logical expressions.

  • Identity Laws: A variable OR-ed with false is the variable itself. A variable AND-ed with true is the variable itself.
    • \(p \lor F \equiv p\)
    • \(p \land T \equiv p\)
  • Domination Laws: Any variable OR-ed with true is always true. Any variable AND-ed with false is always false.
    • \(p \lor T \equiv T\)
    • \(p \land F \equiv F\)
  • Idempotent Laws: OR-ing or AND-ing a variable with itself does not change its value.
    • \(p \lor p \equiv p\)
    • \(p \land p \equiv p\)
  • Double Negation Law: Negating a negation cancels out.
    • \(\neg(\neg p) \equiv p\)
  • Commutative Laws: The order of variables does not matter for AND and OR operations.
    • \(p \lor q \equiv q \lor p\)
    • \(p \land q \equiv q \land p\)
  • Associative Laws: The grouping of variables does not matter for a sequence of the same operator (AND or OR).
    • \((p \lor q) \lor r \equiv p \lor (q \lor r)\)
    • \((p \land q) \land r \equiv p \land (q \land r)\)
  • Distributive Laws: An operator can be distributed over another within parentheses.
    • \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
    • \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
  • De Morgan’s Laws: These laws describe how to negate a conjunction or a disjunction. To do this, you negate each term and flip the operator.
    • \(\neg(p \land q) \equiv \neg p \lor \neg q\)
    • \(\neg(p \lor q) \equiv \neg p \land \neg q\)
  • Absorption Laws: These laws simplify expressions where a variable is combined with an expression containing that same variable.
    • \(p \lor (p \land q) \equiv p\)
    • \(p \land (p \lor q) \equiv p\)
  • Implication and Bi-implication Equivalences: These are fundamental for rewriting conditional statements.
    • Implication: \(p \to q \equiv \neg p \lor q\)
    • Contrapositive: \(p \to q \equiv \neg q \to \neg p\)
    • Bi-implication: \(p \leftrightarrow q \equiv (p \to q) \land (q \to p)\) and \(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\)
1.4 Normal Forms

A normal form in logic is a standardized way of writing a formula. Two of the most common are Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF).

  • Disjunctive Normal Form (DNF): A formula is in DNF if it is a disjunction (ORs) of conjunctions (ANDs) of literals. A literal is a variable or its negation (e.g., \(p\) or \(\neg p\)).
    • Example: \((p \land q) \lor (\neg p \land r)\)
    • To create a DNF from a truth table, you identify all rows where the output is true. For each such row, you create a conjunction (an AND clause) that is true for that specific combination of inputs. Finally, you connect all these conjunctions with disjunctions (ORs).
  • Conjunctive Normal Form (CNF): A formula is in CNF if it is a conjunction (ANDs) of disjunctions (ORs) of literals.
    • Example: \((p \lor q) \land (\neg p \lor r)\)
    • To create a CNF from a truth table, you identify all rows where the output is false. For each such row, you create a disjunction (an OR clause) that is false for that specific combination. Finally, you connect all these disjunctions with conjunctions (ANDs).
1.5 Algebraic Normal Form (ANF)

Algebraic Normal Form (ANF), also known as a Zhegalkin polynomial, is a unique way to represent any logical formula using only two operators: XOR (\(\oplus\)) and AND (\(\cdot\)). The calculations are performed modulo 2, which means that \(1 + 1 = 0\). This form is a polynomial where variables can only have a power of 1 (since \(x \cdot x = x\)).

The key conversion formulas are:

  • \(\neg p \equiv p \oplus 1\)
  • \(p \land q \equiv p \cdot q\) (or just \(pq\))
  • \(p \lor q \equiv p \oplus q \oplus pq\)
  • \(p \to q \equiv 1 \oplus p \oplus pq\)
  • \(p \leftrightarrow q \equiv 1 \oplus x \oplus y\)

Important properties in modulo 2 arithmetic include:

  • \(p \oplus p \equiv 0\)
  • \(p \cdot p \equiv p\) (or \(p^2 \equiv p\))

2. Definitions

  • Tautology: A logical formula that is always true for any assignment of truth values to its variables.
  • Contradiction: A logical formula that is always false for any assignment of truth values to its variables.
  • Contingency: A logical formula that can be either true or false depending on the truth values of its variables.
  • Satisfiability: The property of a formula for which there is at least one assignment of truth values that makes it true.
  • Logical Equivalence: The relationship between two formulas that have identical truth tables.
  • Literal: A propositional variable or its negation (e.g., \(p\) or \(\neg p\)).
  • Disjunctive Normal Form (DNF): A logical formula expressed as a disjunction (OR) of one or more conjunctions (ANDs) of literals.
  • Conjunctive Normal Form (CNF): A logical formula expressed as a conjunction (AND) of one or more disjunctions (ORs) of literals.
  • Algebraic Normal Form (ANF): A canonical representation of a logical formula as a polynomial over a two-element field, using XOR (addition) and AND (multiplication). Also known as a Zhegalkin polynomial.

3. Formulas

  • Identity Law: \(p \lor 0 \equiv p\)
  • Identity Law: \(p \land 1 \equiv p\)
  • Complement Law: \(p \lor \neg p \equiv 1\)
  • Complement Law: \(p \land \neg p \equiv 0\)
  • Idempotent Law: \(p \land p \equiv p\)
  • Idempotent Law: \(p \lor p \equiv p\)
  • Double Negation Law: \(\neg(\neg p) \equiv p\)
  • Associative Law: \((p \lor q) \lor r \equiv p \lor (q \lor r)\)
  • Distributive Law: \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
  • Distributive Law: \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
  • De Morgan’s Law: \(\neg(p \land q) \equiv \neg p \lor \neg q\)
  • De Morgan’s Law: \(\neg(p \lor q) \equiv \neg p \land \neg q\)
  • Implication Equivalence: \(p \to q \equiv \neg p \lor q\)
  • Bi-implication Equivalence: \(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\)
  • Adjacency Law: \(p \lor (\neg p \land q) \equiv p \lor q\)
  • Simplification Law: \((p \lor q) \land (p \lor \neg q) \equiv p\)
  • ANF Conjunction: \(p \land q \equiv pq\)
  • ANF Negation: \(\neg p \equiv p \oplus 1\)
  • ANF Disjunction: \(p \lor q \equiv p \oplus q \oplus pq\)
  • ANF Implication: \(p \to q \equiv 1 \oplus p \oplus pq\)
  • ANF Bi-implication: \(p \leftrightarrow q \equiv 1 \oplus p \oplus q\)
  • ANF Property (Idempotence): \(p \cdot p \equiv p\)
  • ANF Property (XOR with self): \(p \oplus p \equiv 0\)
  • ANF Property (XOR Identity): \(p \oplus 0 \equiv p\)

4. Examples

4.1. Prove an Identity (Lab 2, Task 1.a)

Prove that \(¬¬a ≡ a\).

Click to see the solution
  1. Set up truth table: We need columns for the variable \(a\), its negation \(¬a\), and its double negation \(¬¬a\).
  2. Evaluate \(¬a\): This column contains the opposite truth values of \(a\).
  3. Evaluate \(¬¬a\): This column contains the opposite truth values of \(¬a\).
  4. Compare columns: Compare the first column (\(a\)) with the last column (\(¬¬a\)).
a ¬a ¬¬a
0 1 0
1 0 1
Answer: The columns for \(a\) and \(¬¬a\) are identical, which proves the equivalence.
4.2. Prove an Identity (Lab 2, Task 1.b)

Prove that \(a ↔ b ≡ (a ∧ b) ∨ (¬a ∧ ¬b)\).

Click to see the solution
  1. Set up truth table: We need columns for \(a, b\), the left side (\(a ↔ b\)), and the right side, including intermediate steps.
  2. Evaluate left side (\(a ↔ b\)): The biconditional is true only when \(a\) and \(b\) have the same truth value.
  3. Evaluate right side:
    • Calculate \(a ∧ b\).
    • Calculate \(¬a ∧ ¬b\).
    • Calculate the disjunction of the previous two results.
  4. Compare final columns:
a b a ↔︎ b a ∧ b ¬a ¬b ¬a ∧ ¬b (a ∧ b) ∨ (¬a ∧ ¬b)
0 0 1 0 1 1 1 1
0 1 0 0 1 0 0 0
1 0 0 0 0 1 0 0
1 1 1 1 0 0 0 1
Answer: The columns for \(a ↔ b\) and \((a ∧ b) ∨ (¬a ∧ ¬b)\) are identical, proving the equivalence.
4.3. Prove an Identity (Lab 2, Task 1.c)

Prove that \(¬a ∧ (b ∨ ¬c) ≡ (¬a ∧ b) ∨ (¬a ∧ ¬c)\). This is an example of the distributive law.

Click to see the solution
  1. Set up truth table: Create columns for \(a, b, c\) and both sides of the equivalence.
  2. Evaluate left side:
    • Calculate \(b ∨ ¬c\).
    • Calculate the conjunction of the result with \(¬a\).
  3. Evaluate right side:
    • Calculate \(¬a ∧ b\).
    • Calculate \(¬a ∧ ¬c\).
    • Calculate the disjunction of the two previous results.
  4. Compare final columns:
a b c ¬a ¬c b ∨ ¬c ¬a ∧ (b ∨ ¬c) ¬a ∧ b ¬a ∧ ¬c (¬a ∧ b) ∨ (¬a ∧ ¬c)
0 0 0 1 1 1 1 0 1 1
0 0 1 1 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 0 1
1 0 0 0 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0
1 1 0 0 1 1 0 0 0 0
1 1 1 0 0 1 0 0 0 0
Answer: The final columns for both expressions are identical, proving the distributive law.
4.4. Apply Negation and Simplify (Lab 2, Task 2)

Apply the negation and simplify (using De Morgan’s laws) for \(¬a ∧ (b ∨ c)\).

Click to see the solution
  1. Apply negation: We start with \(¬(¬a ∧ (b ∨ c))\).
  2. Use De Morgan’s law for conjunction: \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\).
    • \(¬(¬a) ∨ ¬(b ∨ c)\)
  3. Apply double negation: \(¬(¬a) ≡ a\).
    • \(a ∨ ¬(b ∨ c)\)
  4. Use De Morgan’s law for disjunction: \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\).
    • \(a ∨ (¬b ∧ ¬c)\)
Answer: The simplified expression is \(a ∨ (¬b ∧ ¬c)\).
4.5. Apply Negation and Simplify (Lab 2, Task 2.a)

Apply the negation and simplify (using De Morgan’s laws) for \(¬a ∨ (¬b ∧ c)\).

Click to see the solution
  1. Apply negation: \(¬(¬a ∨ (¬b ∧ c))\)
  2. Apply De Morgan’s law for disjunction: \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\).
    • \(¬(¬a) ∧ ¬(¬b ∧ c)\)
  3. Apply double negation: \(¬(¬a) ≡ a\).
    • \(a ∧ ¬(¬b ∧ c)\)
  4. Apply De Morgan’s law for conjunction: \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\).
    • \(a ∧ (¬(¬b) ∨ ¬c)\)
  5. Apply double negation: \(¬(¬b) ≡ b\).
    • \(a ∧ (b ∨ ¬c)\)
Answer: The simplified expression is \(a ∧ (b ∨ ¬c)\).
4.6. Apply Negation and Simplify (Lab 2, Task 2.b)

Apply the negation and simplify (using De Morgan’s laws) for \((¬a ∨ b) ∧ (c ∨ ¬d)\).

Click to see the solution
  1. Apply negation: \(¬((¬a ∨ b) ∧ (c ∨ ¬d))\)
  2. Apply De Morgan’s law for conjunction: \(¬(X ∧ Y) ≡ ¬X ∨ ¬Y\).
    • \(¬(¬a ∨ b) ∨ ¬(c ∨ ¬d)\)
  3. Apply De Morgan’s law for disjunction to both terms: \(¬(X ∨ Y) ≡ ¬X ∧ ¬Y\).
    • \((¬(¬a) ∧ ¬b) ∨ (¬c ∧ ¬(¬d))\)
  4. Apply double negation:
    • \((a ∧ ¬b) ∨ (¬c ∧ d)\)
Answer: The simplified expression is \((a ∧ ¬b) ∨ (¬c ∧ d)\).
4.7. Apply Negation and Simplify (Lab 2, Task 2.c)

Apply the negation and simplify (using De Morgan’s laws) for \(x₁ ∧ (x₂ ∨ x₃ ∨ (x₄ ∧ x₅))\).

Click to see the solution
  1. Apply negation: \(¬(x₁ ∧ (x₂ ∨ x₃ ∨ (x₄ ∧ x₅)))\)
  2. Apply De Morgan’s law (outer conjunction):
    • \(¬x₁ ∨ ¬(x₂ ∨ x₃ ∨ (x₄ ∧ x₅))\)
  3. Apply De Morgan’s law (disjunction):
    • \(¬x₁ ∨ (¬x₂ ∧ ¬x₃ ∧ ¬(x₄ ∧ x₅))\)
  4. Apply De Morgan’s law (inner conjunction):
    • \(¬x₁ ∨ (¬x₂ ∧ ¬x₃ ∧ (¬x₄ ∨ ¬x₅))\)
Answer: The simplified expression is \(¬x₁ ∨ (¬x₂ ∧ ¬x₃ ∧ (¬x₄ ∨ ¬x₅))\).
4.8. Find and Simplify DNF (Lab 2, Task 3)

Find DNF from the truth table and simplify (using Distributive laws): \(Φ(x, y) ≡ (1110)\).

Click to see the solution
  1. Construct the truth table and identify minterms:
x y Φ(x, y) Minterm
0 0 1 ¬x ∧ ¬y
0 1 1 ¬x ∧ y
1 0 1 x ∧ ¬y
1 1 0
  1. Write the full DNF:
    • \((¬x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ ¬y)\)
  2. Simplify using distributive laws:
    • Factor \(¬x\) from the first two terms: \(¬x ∧ (¬y ∨ y) ∨ (x ∧ ¬y)\)
    • Apply the law \(A ∨ ¬A ≡ 1\): \(¬x ∧ 1 ∨ (x ∧ ¬y)\)
    • Apply the law \(A ∧ 1 ≡ A\): \(¬x ∨ (x ∧ ¬y)\)
    • Apply the distributive law \(A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C)\): \((¬x ∨ x) ∧ (¬x ∨ ¬y)\)
    • Apply the law \(A ∨ ¬A ≡ 1\): \(1 ∧ (¬x ∨ ¬y)\)
    • Apply the law \(1 ∧ A ≡ A\): \(¬x ∨ ¬y\)
Answer: The simplified DNF is \(¬x ∨ ¬y\).
4.9. Find and Simplify DNF (Lab 2, Task 3.a)

Find DNF from the truth table and simplify (using Distributive laws): \(Φ(x,y,z) ≡ (01111110)\).

Click to see the solution
  1. Identify minterms (rows where Φ is 1):
    • (0,0,1) → \(¬x ∧ ¬y ∧ z\)
    • (0,1,0) → \(¬x ∧ y ∧ ¬z\)
    • (0,1,1) → \(¬x ∧ y ∧ z\)
    • (1,0,0) → \(x ∧ ¬y ∧ ¬z\)
    • (1,0,1) → \(x ∧ ¬y ∧ z\)
    • (1,1,0) → \(x ∧ y ∧ ¬z\)
  2. Write the full DNF:
    • \((¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ ¬z)\)
  3. Simplify by grouping:
    • Group 1: \((¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ z) = (¬x ∨ x) ∧ (¬y ∨ y) ∧ z\) -> This grouping is incorrect. Let’s group pairs.
    • Group by \(¬x\): \(¬x ∧ ((¬y ∧ z) ∨ (y ∧ ¬z) ∨ (y ∧ z))\)
    • Group by \(x\): \(x ∧ ((¬y ∧ ¬z) ∨ (¬y ∧ z) ∨ (y ∧ ¬z))\)
    • Let’s try a different grouping:
    • \((¬x ∧ z) ∧ (¬y ∨ y) = ¬x ∧ z\)
    • \((x ∧ ¬y) ∧ (¬z ∨ z) = x ∧ ¬y\)
    • \((y ∧ ¬z) ∧ (¬x ∨ x) = y ∧ ¬z\)
    • Let’s check:
    • $ (¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ z) = ¬x ∧ z $
    • $ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) = x ∧ ¬y $
    • $ (¬x ∧ y ∧ ¬z) ∨ (x ∧ y ∧ ¬z) = y ∧ ¬z $
  4. Combine the simplified terms:
    • \((¬x ∧ z) ∨ (x ∧ ¬y) ∨ (y ∧ ¬z)\)
Answer: The simplified DNF is \((¬x ∧ z) ∨ (x ∧ ¬y) ∨ (y ∧ ¬z)\).
4.10. Find and Simplify CNF (Lab 2, Task 4)

Find CNF from the truth table and simplify (using Distributive laws): \(Ψ(x,y,z) ≡ (00110000)\).

Click to see the solution
  1. Identify maxterms (rows where Ψ is 0):
    • (0,0,0) → \(x ∨ y ∨ z\)
    • (0,0,1) → \(x ∨ y ∨ ¬z\)
    • (1,0,0) → \(¬x ∨ y ∨ z\)
    • (1,0,1) → \(¬x ∨ y ∨ ¬z\)
    • (1,1,0) → \(¬x ∨ ¬y ∨ z\)
    • (1,1,1) → \(¬x ∨ ¬y ∨ ¬z\)
  2. Write the full CNF:
    • \((x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)\)
  3. Simplify by grouping (using $ (A ∨ B) ∧ (A ∨ ¬B) ≡ A $):
    • Group 1 & 2: \(((x ∨ y) ∨ z) ∧ ((x ∨ y) ∨ ¬z) = (x ∨ y)\)
    • Group 3 & 4: \(((¬x ∨ y) ∨ z) ∧ ((¬x ∨ y) ∨ ¬z) = (¬x ∨ y)\)
    • Group 5 & 6: \(((¬x ∨ ¬y) ∨ z) ∧ ((¬x ∨ ¬y) ∨ ¬z) = (¬x ∨ ¬y)\)
  4. Combine the simplified terms:
    • \((x ∨ y) ∧ (¬x ∨ y) ∧ (¬x ∨ ¬y)\)
  5. Further simplification:
    • Group the first two terms: \(((x ∧ ¬x) ∨ y) ∧ (¬x ∨ ¬y) = (0 ∨ y) ∧ (¬x ∨ ¬y) = y ∧ (¬x ∨ ¬y)\)
    • Distribute: \((y ∧ ¬x) ∨ (y ∧ ¬y) = (y ∧ ¬x) ∨ 0 = y ∧ ¬x\)
    • The result is in DNF, not CNF. Let’s simplify the CNF differently.
    • From \((x ∨ y) ∧ (¬x ∨ y) ∧ (¬x ∨ ¬y)\), group the last two terms: \((x ∨ y) ∧ (¬x ∨ (y ∧ ¬y)) = (x ∨ y) ∧ (¬x ∨ 0) = (x ∨ y) ∧ ¬x\)
    • Distribute: \((x ∧ ¬x) ∨ (y ∧ ¬x) = 0 ∨ (y ∧ ¬x) = y ∧ ¬x\). Still DNF.
    • Let’s check the truth table of the simplified CNF \((x ∨ y) ∧ (¬x ∨ y) ∧ (¬x ∨ ¬y)\). It simplifies to \(y ∧ (¬x ∨ ¬y)\), which is \(¬x ∧ y\). Let’s test the original vector. It is (00110000). The function is true for (0,1,0) and (0,1,1). The expression \(¬x ∧ y\) is true for these rows. So the simplification is correct. The simplest CNF form is often harder to reach via algebraic manipulation. Let’s simplify from the DNF. The DNF is \((¬x ∧ y ∧ ¬z) ∨ (¬x ∧ y ∧ z) = ¬x ∧ y\). This is already the simplest form. To get a CNF, we use distributive laws: \(¬x ∧ y\). This doesn’t look like a standard CNF. However, if we take the simplified CNF: \((y) ∧ (¬x ∨ ¬y)\) which is \((y) ∧ (¬x ∨ y) ∧ (x ∨ ¬y)\). Let’s use the final result from the first simplification step.
Answer: The simplified CNF is \((x ∨ y) ∧ (¬x ∨ y) ∧ (¬x ∨ ¬y)\). A further simplification yields \(y ∧ (¬x ∨ ¬y)\).
4.11. Find Algebraic Normal Form (Lab 2, Task 5.a)

Find Algebraic Normal Form for: \((a → ¬b) ∧ (b → a)\)

Click to see the solution
  1. Convert logical operators to ANF expressions:
    • \(A → B\) becomes \(1 ⊕ A ⊕ AB\).
    • \(¬B\) becomes \(B ⊕ 1\).
    • \(a → ¬b\) becomes \(1 ⊕ a ⊕ a(b ⊕ 1) = 1 ⊕ a ⊕ ab ⊕ a = 1 ⊕ ab ⊕ (a ⊕ a) = 1 ⊕ ab\).
    • \(b → a\) becomes \(1 ⊕ b ⊕ ba\).
  2. Combine the expressions with AND (multiplication):
    • \((1 ⊕ ab) · (1 ⊕ b ⊕ ab)\)
  3. Expand the expression:
    • \(1(1 ⊕ b ⊕ ab) ⊕ ab(1 ⊕ b ⊕ ab)\)
    • \(1 ⊕ b ⊕ ab ⊕ ab ⊕ abb ⊕ abab\)
  4. Simplify using \(X ⊕ X = 0\) and \(X·X = X\):
    • \(1 ⊕ b ⊕ (ab ⊕ ab) ⊕ ab ⊕ ab\)
    • \(1 ⊕ b ⊕ 0 ⊕ ab ⊕ ab\)
    • \(1 ⊕ b ⊕ 0 = 1 ⊕ b\)
Answer: The Algebraic Normal Form is \(1 ⊕ b\) (which is equivalent to \(¬b\)).
4.12. Find Algebraic Normal Form (Lab 2, Task 5.b)

Find Algebraic Normal Form for: \((¬a ↔ b) → ¬b\)

Click to see the solution
  1. Convert the inner expressions to ANF:
    • \(¬a ↔ b\): is \(1 ⊕ (a ⊕ 1) ⊕ b = 1 ⊕ a ⊕ 1 ⊕ b = a ⊕ b\).
    • \(¬b\): is \(b ⊕ 1\).
  2. Apply the implication formula \(X → Y ≡ 1 ⊕ X ⊕ XY\):
    • Let \(X = a ⊕ b\) and \(Y = b ⊕ 1\).
    • \(1 ⊕ (a ⊕ b) ⊕ (a ⊕ b)(b ⊕ 1)\)
  3. Expand and simplify:
    • \(1 ⊕ a ⊕ b ⊕ (ab ⊕ a ⊕ b^2 ⊕ b)\)
    • \(1 ⊕ a ⊕ b ⊕ (ab ⊕ a ⊕ b ⊕ b)\)
    • \(1 ⊕ a ⊕ b ⊕ ab ⊕ a ⊕ 0\)
    • \(1 ⊕ (a ⊕ a) ⊕ b ⊕ ab\)
    • \(1 ⊕ 0 ⊕ b ⊕ ab = 1 ⊕ b ⊕ ab\)
Answer: The Algebraic Normal Form is \(1 ⊕ b ⊕ ab\).
4.13. Find Algebraic Normal Form (Lab 2, Task 5.c)

Find Algebraic Normal Form for: \((b → ¬a) ↔ (a ∨ ¬b)\)

Click to see the solution
  1. Convert both sides to ANF:
    • Left side (LS): \(b → ¬a\)
      • \(1 ⊕ b ⊕ b(a ⊕ 1) = 1 ⊕ b ⊕ ab ⊕ b = 1 ⊕ ab ⊕ (b ⊕ b) = 1 ⊕ ab\).
    • Right side (RS): \(a ∨ ¬b\)
      • \(a ⊕ (b ⊕ 1) ⊕ a(b ⊕ 1) = a ⊕ b ⊕ 1 ⊕ ab ⊕ a = (a ⊕ a) ⊕ b ⊕ 1 ⊕ ab = b ⊕ ab ⊕ 1\).
  2. Apply the biconditional formula \(X ↔ Y ≡ 1 ⊕ X ⊕ Y\):
    • \(1 ⊕ (1 ⊕ ab) ⊕ (b ⊕ ab ⊕ 1)\)
  3. Simplify:
    • \(1 ⊕ 1 ⊕ ab ⊕ b ⊕ ab ⊕ 1\)
    • \((1 ⊕ 1) ⊕ (ab ⊕ ab) ⊕ b ⊕ 1\)
    • \(0 ⊕ 0 ⊕ b ⊕ 1 = b ⊕ 1\)
Answer: The Algebraic Normal Form is \(b ⊕ 1\) (which is equivalent to \(¬b\)).
4.14. Find Algebraic Normal Form (Lab 2, Task 5.d)

Find Algebraic Normal Form for: \((a → ¬b) ∧ (¬c ∨ ¬a)\)

Click to see the solution
  1. Convert both parts to ANF:
    • Part 1: \(a → ¬b\)
      • \(1 ⊕ a ⊕ a(b ⊕ 1) = 1 ⊕ a ⊕ ab ⊕ a = 1 ⊕ ab\).
    • Part 2: \(¬c ∨ ¬a\)
      • \((c ⊕ 1) ∨ (a ⊕ 1)\) becomes \((c ⊕ 1) ⊕ (a ⊕ 1) ⊕ (c ⊕ 1)(a ⊕ 1)\)
      • \(c ⊕ 1 ⊕ a ⊕ 1 ⊕ (ac ⊕ c ⊕ a ⊕ 1) = c ⊕ a ⊕ ac ⊕ c ⊕ a ⊕ 1 = ac ⊕ 1\).
  2. Combine with AND (multiplication):
    • \((1 ⊕ ab) · (1 ⊕ ac)\)
  3. Expand and simplify:
    • \(1 ⊕ ac ⊕ ab ⊕ abac = 1 ⊕ ac ⊕ ab ⊕ abc\).
Answer: The Algebraic Normal Form is \(1 ⊕ ab ⊕ ac ⊕ abc\).
4.15. Find Algebraic Normal Form (Lab 2, Task 5.e)

Find Algebraic Normal Form for: \((a ∧ ¬c) ↔ (c → ¬b)\)

Click to see the solution
  1. Convert both sides to ANF:
    • Left side (LS): \(a ∧ ¬c\)
      • \(a(c ⊕ 1) = ac ⊕ a\).
    • Right side (RS): \(c → ¬b\)
      • \(1 ⊕ c ⊕ c(b ⊕ 1) = 1 ⊕ c ⊕ cb ⊕ c = 1 ⊕ cb\).
  2. Apply the biconditional formula \(X ↔ Y ≡ 1 ⊕ X ⊕ Y\):
    • \(1 ⊕ (ac ⊕ a) ⊕ (1 ⊕ cb)\)
  3. Simplify:
    • \(1 ⊕ ac ⊕ a ⊕ 1 ⊕ bc\)
    • \((1 ⊕ 1) ⊕ a ⊕ ac ⊕ bc = a ⊕ ac ⊕ bc\).
Answer: The Algebraic Normal Form is \(a ⊕ ac ⊕ bc\).
4.16. Find Algebraic Normal Form (Lab 2, Task 5.f)

Find Algebraic Normal Form for: \((¬a → ¬c) ∨ (a ↔ b)\)

Click to see the solution
  1. Convert both parts to ANF:
    • Part 1: \(¬a → ¬c\)
      • \(1 ⊕ (a ⊕ 1) ⊕ (a ⊕ 1)(c ⊕ 1) = 1 ⊕ a ⊕ 1 ⊕ (ac ⊕ a ⊕ c ⊕ 1) = a ⊕ ac ⊕ a ⊕ c ⊕ 1 = ac ⊕ c ⊕ 1\).
    • Part 2: \(a ↔ b\)
      • \(1 ⊕ a ⊕ b\).
  2. Apply the disjunction formula \(X ∨ Y ≡ X ⊕ Y ⊕ XY\):
    • Let \(X = ac ⊕ c ⊕ 1\) and \(Y = 1 ⊕ a ⊕ b\).
    • \((ac ⊕ c ⊕ 1) ⊕ (1 ⊕ a ⊕ b) ⊕ (ac ⊕ c ⊕ 1)(1 ⊕ a ⊕ b)\)
  3. Simplify the expression:
    • First part: \(ac ⊕ c ⊕ 1 ⊕ 1 ⊕ a ⊕ b = ac ⊕ c ⊕ a ⊕ b\).
    • Second part (product): \((ac ⊕ c ⊕ 1)(1 ⊕ a ⊕ b) = (ac(1⊕a⊕b) ⊕ c(1⊕a⊕b) ⊕ 1(1⊕a⊕b))\)
    • \(= (ac⊕abc⊕abc) ⊕ (c⊕ac⊕bc) ⊕ (1⊕a⊕b)\)
    • \(= ac ⊕ c ⊕ ac ⊕ bc ⊕ 1 ⊕ a ⊕ b = c ⊕ bc ⊕ 1 ⊕ a ⊕ b\).
  4. Combine everything:
    • \((ac ⊕ c ⊕ a ⊕ b) ⊕ (c ⊕ bc ⊕ 1 ⊕ a ⊕ b)\)
    • \(ac ⊕ (c ⊕ c) ⊕ (a ⊕ a) ⊕ (b ⊕ b) ⊕ bc ⊕ 1\)
    • \(ac ⊕ 0 ⊕ 0 ⊕ 0 ⊕ bc ⊕ 1 = ac ⊕ bc ⊕ 1\).
Answer: The Algebraic Normal Form is \(ac ⊕ bc ⊕ 1\).
4.17. Prove an Identity Using a Truth Table (Tutorial 2, Task 1)

Prove that \(a ∨ 0 ≡ a\).

Click to see the solution
  1. Set up columns: We need columns for the variable \(a\), the constant \(0\) (False), and the expression \(a ∨ 0\).
  2. List input combinations: The variable \(a\) can be either true (1) or false (0).
  3. Evaluate \(a ∨ 0\): The disjunction is true if either operand is true. When \(a\) is 1, the result is 1. When \(a\) is 0, the result is 0.
  4. Compare columns: Compare the column for \(a\) with the column for \(a ∨ 0\).
a 0 a ∨ 0
0 0 0
1 0 1
Answer: Since the truth values in the column for \(a\) are identical to the truth values in the column for \(a ∨ 0\), the equivalence \(a ∨ 0 ≡ a\) is proven.
4.18. Prove an Identity Using a Truth Table (Tutorial 2, Task 2)

Prove that \(a → b ≡ ¬a ∨ b\).

Click to see the solution
  1. Set up columns: We need columns for variables \(a\) and \(b\), the expression \(a → b\), and the expression \(¬a ∨ b\).
  2. List input combinations: For two variables, there are four possible combinations.
  3. Evaluate \(a → b\): This is false only when \(a\) is true and \(b\) is false.
  4. Evaluate \(¬a ∨ b\): First find \(¬a\), then find the disjunction with \(b\).
  5. Compare columns: Compare the final columns for both expressions.
a b a → b ¬a ¬a ∨ b
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1
Answer: The columns for \(a → b\) and \(¬a ∨ b\) are identical, which proves the equivalence \(a → b ≡ ¬a ∨ b\).
4.19. Prove an Identity Using a Truth Table (Tutorial 2, Task 3)

Prove that \(a ∨ (¬a ∧ b) ≡ a ∨ b\).

Click to see the solution
  1. Set up columns: We need columns for \(a, b\), intermediate expressions like \(¬a\) and \(¬a ∧ b\), and the two final expressions \(a ∨ (¬a ∧ b)\) and \(a ∨ b\).
  2. List input combinations: There are four combinations for two variables.
  3. Evaluate left side: Calculate the truth values for \(a ∨ (¬a ∧ b)\).
  4. Evaluate right side: Calculate the truth values for \(a ∨ b\).
  5. Compare results: Check if the final columns for both sides of the equivalence are identical.
a b ¬a ¬a ∧ b a ∨ (¬a ∧ b) a ∨ b
0 0 1 0 0 0
0 1 1 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1
Answer: The truth values for \(a ∨ (¬a ∧ b)\) and \(a ∨ b\) are identical for all input combinations, proving the equivalence.
4.20. Apply Negation and Simplify (Tutorial 2, Task 4)

Apply the negation to the expression \(¬a ∧ (b ∨ c)\) and simplify using De Morgan’s laws.

Click to see the solution
  1. Apply negation: We need to find the negation of the entire expression: \(¬(¬a ∧ (b ∨ c))\).
  2. Use De Morgan’s law for conjunction: ¬(X ∧ Y) ≡ ¬X ∨ ¬Y.
    • \(¬(¬a) ∨ ¬(b ∨ c)\)
  3. Apply double negation rule: ¬(¬a) ≡ a.
    • \(a ∨ ¬(b ∨ c)\)
  4. Use De Morgan’s law for disjunction: ¬(X ∨ Y) ≡ ¬X ∧ ¬Y.
    • \(a ∨ (¬b ∧ ¬c)\)
Answer: The simplified expression is \(a ∨ (¬b ∧ ¬c)\).
4.21. Apply Negation and Simplify (Tutorial 2, Task 5)

Apply the negation to the expression \(a ∧ (¬b ∨ (c ∧ ¬d))\) and simplify using De Morgan’s laws.

Click to see the solution
  1. Apply negation: We start with the negation of the whole expression: \(¬(a ∧ (¬b ∨ (c ∧ ¬d)))\).
  2. Apply De Morgan’s Law (outer): Apply ¬(X ∧ Y) ≡ ¬X ∨ ¬Y.
    • \(¬a ∨ ¬(¬b ∨ (c ∧ ¬d))\)
  3. Apply De Morgan’s Law (inner disjunction): Apply ¬(X ∨ Y) ≡ ¬X ∧ ¬Y.
    • \(¬a ∨ (¬(¬b) ∧ ¬(c ∧ ¬d))\)
  4. Apply Double Negation: Apply ¬(¬b) ≡ b.
    • \(¬a ∨ (b ∧ ¬(c ∧ ¬d))\)
  5. Apply De Morgan’s Law (inner conjunction): Apply ¬(X ∧ Y) ≡ ¬X ∨ ¬Y.
    • \(¬a ∨ (b ∧ (¬c ∨ ¬(¬d)))\)
  6. Apply Double Negation: Apply ¬(¬d) ≡ d.
    • \(¬a ∨ (b ∧ (¬c ∨ d))\)
Answer: The simplified expression is \(¬a ∨ (b ∧ (¬c ∨ d))\).
4.22. Find and Simplify DNF (Tutorial 2, Task 6)

Find the Disjunctive Normal Form (DNF) from the truth table \(Φ(x, y) ≡ (1110)\) and simplify the result.

Click to see the solution
  1. Construct the truth table: The vector (1110) corresponds to the function’s output.
x y Φ(x, y)
0 0 1
0 1 1
1 0 1
1 1 0
  1. Write the DNF: The DNF is the disjunction of minterms for each row where the function is 1.
    • Row 1 (x=0, y=0): \(¬x ∧ ¬y\)
    • Row 2 (x=0, y=1): \(¬x ∧ y\)
    • Row 3 (x=1, y=0): \(x ∧ ¬y\)
    • DNF: \((¬x ∧ ¬y) ∨ (¬x ∧ y) ∨ (x ∧ ¬y)\)
  2. Simplify the expression:
    • Factor out \(¬x\) from the first two terms: \(¬x ∧ (¬y ∨ y) ∨ (x ∧ ¬y)\)
    • Since \((¬y ∨ y) ≡ 1\), this simplifies to: \((¬x ∧ 1) ∨ (x ∧ ¬y)\)
    • This becomes: \(¬x ∨ (x ∧ ¬y)\)
    • Using the distribution law (X ∨ (Y ∧ Z) ≡ (X ∨ Y) ∧ (X ∨ Z)): \((¬x ∨ x) ∧ (¬x ∨ ¬y)\)
    • Since \((¬x ∨ x) ≡ 1\): \(1 ∧ (¬x ∨ ¬y)\)
    • The final result is: \(¬x ∨ ¬y\)
Answer: The simplified DNF is \(¬x ∨ ¬y\).
4.23. Prove an Identity (Tutorial 2, Task 7)

Prove that \(x^n ≡ x\). This is interpreted as the idempotence law, e.g., \(x ∧ x ≡ x\).

Click to see the solution
  1. Interpret the expression: In Boolean algebra, exponentiation is equivalent to repeated conjunction (AND). Therefore, \(x^n\) means \(x ∧ x ∧ ... ∧ x\), which simplifies to just \(x ∧ x\) due to the nature of the logic. The property is called idempotence. We will prove \(x ∧ x ≡ x\).
  2. Set up truth table: We need a column for \(x\) and a column for \(x ∧ x\).
  3. Evaluate \(x ∧ x\): The result is 1 if and only if both operands (both \(x\)) are 1.
  4. Compare columns:
x x ∧ x
0 0
1 1
Answer: The columns for \(x\) and \(x ∧ x\) are identical, proving the idempotence law.
4.24. Prove an Identity with XOR (Tutorial 2, Task 8)

Prove that \(x ⊕ x ≡ 0\).

Click to see the solution
  1. Set up truth table: We need a column for the input \(x\) and the output \(x ⊕ x\).
  2. Recall XOR (⊕) definition: The result of XOR is 1 if the inputs are different, and 0 if they are the same.
  3. Evaluate \(x ⊕ x\): Since the inputs are always the same (both 0 or both 1), the result is always 0.
x x ⊕ x
0 0 ⊕ 0 = 0
1 1 ⊕ 1 = 0
Answer: The column for \(x ⊕ x\) is always 0, proving that \(x ⊕ x ≡ 0\).
4.25. Disprove an Identity with XOR (Tutorial 2, Task 9)

Prove that \(x ⊕ (y · z) ≠ (x ⊕ y) · (x ⊕ z)\).

Click to see the solution
  1. Find a counterexample: To disprove an identity, we only need to find one assignment of truth values for the variables where the two sides of the expression are not equal.
  2. Set up a truth table: We will evaluate both sides of the expression. The operator · represents AND.
  3. Try a combination: Let’s test the case where \(x=1, y=1, z=0\).
  4. Evaluate the left side: \(x ⊕ (y · z)\)
    • \(1 ⊕ (1 · 0) = 1 ⊕ 0 = 1\)
  5. Evaluate the right side: \((x ⊕ y) · (x ⊕ z)\)
    • \((1 ⊕ 1) · (1 ⊕ 0) = 0 · 1 = 0\)
  6. Compare results: For this input combination, the left side evaluates to 1 while the right side evaluates to 0.
Answer: Since we found a case where \(1 ≠ 0\), we have proven that \(x ⊕ (y · z) ≠ (x ⊕ y) · (x ⊕ z)\). XOR is not distributive over AND.
4.26. Find Algebraic Normal Form (Tutorial 2, Task 10)

Find the Algebraic Normal Form (ANF) of \((x^2 ⊕ xy ⊕ 1) ⊕ (x^2y ⊕ xy^2 ⊕ x ⊕ y ⊕ 1)\).

Click to see the solution
  1. Simplify using Boolean algebra rules: In ANF, multiplication is idempotent, so \(x^2 = x\), \(y^2 = y\). This means \(x^2y = xy\) and \(xy^2 = xy\).
  2. Rewrite the expression:
    • \((x ⊕ xy ⊕ 1) ⊕ (xy ⊕ xy ⊕ x ⊕ y ⊕ 1)\)
  3. Remove parentheses and group like terms: (XOR is associative)
    • \(x ⊕ xy ⊕ 1 ⊕ xy ⊕ xy ⊕ x ⊕ y ⊕ 1\)
    • \((x ⊕ x) ⊕ (xy ⊕ xy ⊕ xy) ⊕ y ⊕ (1 ⊕ 1)\)
  4. Apply the identity \(a ⊕ a = 0\):
    • \(0 ⊕ (xy ⊕ 0) ⊕ y ⊕ 0\)
    • \(0 ⊕ xy ⊕ y ⊕ 0\)
  5. Apply the identity \(a ⊕ 0 = a\):
    • \(xy ⊕ y\)
Answer: The Algebraic Normal Form is \(xy ⊕ y\).
4.27. Find Algebraic Normal Form (Tutorial 2, Task 11)

Find the Algebraic Normal Form for \((a ∧ ¬b) → ¬a\).

Click to see the solution
  1. Convert logical operators to a simpler form: First, replace the implication.
    • \(X → Y ≡ ¬X ∨ Y\)
    • \(¬(a ∧ ¬b) ∨ ¬a\)
  2. Apply De Morgan’s Law:
    • \((¬a ∨ ¬(¬b)) ∨ ¬a\)
    • \((¬a ∨ b) ∨ ¬a\)
  3. Apply associative and idempotent laws:
    • \(¬a ∨ b\)
  4. Convert the simplified expression to ANF:
    • ¬a is represented as \(a ⊕ 1\).
    • \(X ∨ Y\) is represented as \(X ⊕ Y ⊕ XY\).
    • Let \(X = ¬a = a ⊕ 1\) and \(Y = b\).
    • \((a ⊕ 1) ⊕ b ⊕ ((a ⊕ 1)b)\)
  5. Expand and simplify:
    • \(a ⊕ 1 ⊕ b ⊕ (ab ⊕ b)\)
    • \(a ⊕ 1 ⊕ b ⊕ ab ⊕ b\)
    • \(a ⊕ ab ⊕ (b ⊕ b) ⊕ 1\)
    • \(a ⊕ ab ⊕ 0 ⊕ 1\)
    • \(a ⊕ ab ⊕ 1\)
Answer: The Algebraic Normal Form is \(a ⊕ ab ⊕ 1\).
4.28. Find Algebraic Normal Form (Tutorial 2, Task 12)

Find the Algebraic Normal Form for \((¬a ∧ b) ∨ (a ∧ b)\).

Click to see the solution
  1. Simplify the expression using logical laws:
    • We can factor out \(b\) using the distributive law: \((¬a ∨ a) ∧ b\).
    • The term \((¬a ∨ a)\) is a tautology, which is always true (1).
    • The expression becomes \(1 ∧ b\).
    • This simplifies to just \(b\).
  2. Convert to ANF: The expression \(b\) is already in its simplest Algebraic Normal Form.
Answer: The Algebraic Normal Form is \(b\).